package Top_Interview_Questions.Tree;

import Top_Interview_Questions.Tree.Supple.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: 吕庆龙
 * @Date: 2020/2/9 11:34
 * <p>
 * #.怎么遍历树，树有深度优先和广度优先两种遍历方法。复习的时候好好看看。
 * #.广度优先遍历一般用队列实现,复习的时候百度下代码。
 * https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/solution/
 * er-cha-sou-suo-shu-zhong-di-kxiao-de-yuan-su-by-le/
 */
public class _0230 {

    public static void main(String[] args) {
        _0230 test = new _0230();

        TreeNode root = new TreeNode(3);
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(4);
        TreeNode node3 = new TreeNode(2);

        root.left = node1;
        root.right = node2;
        node1.right = node3;

        test.infixOrder(root);
        System.out.println(test.value);
    }



    /*-----------------------------------------自己写的-----------------------------------------*/

    /**
     *     3
     *   /  \
     *  1    4
     *   \
     *    2
     */
    List<Integer> value = new ArrayList<>();
    public int kthSmallest(TreeNode root, int k) {
        infixOrder(root);

        return value.get(k - 1);
    }

    // 中序遍历
    public void infixOrder(TreeNode root) {
        if (root.left != null) {
            infixOrder(root.left);
        }
        value.add(root.val);
        if (root.right != null) {
            infixOrder(root.right);
        }
    }

    /*-----------------------------------------------------------------------------------------*/
}
